﻿namespace LeetCodeProject._0001_1000._001_100._61_70._069;

public class Solution
{
    private static readonly int MAX = (int)Math.Sqrt(int.MaxValue);

    public int MySqrt(int x)
    {
        var low = 0;
        var high = x;
        while (low <= high)
        {
            var mid = low + (high - low) / 2;
            if (mid > MAX)
            {
                high = mid - 1;
                continue;
            }

            var m2 = mid * mid;
            if (m2 == x)
                return mid;
            if (m2 < x)
                low = mid + 1;
            else
                high = mid - 1;
        }

        return low - 1;
    }
}